//
// Created by Incredible on 17/3/15.
//

#ifndef QUICKSORT_MERGESORT_H
#define QUICKSORT_MERGESORT_H

#include <iostream>
#include "SortTestHelper.h"
#include "InsertionSort.h"

using namespace std;

template<typename T>
//合并两个有序数组（采用额外的辅助空间进行合并）
void __merge(T arr[], int l, int mid, int r) {

    T aux[r - l + 1];
    for (int i = l; i <= r; i++) {
        aux[i - l] = arr[i];
    }


    int i = l, j = mid + 1;
    for (int k = l; k <= r; k++) {

        if (i > mid) {
            arr[k] = aux[j - l];
            j++;
        } else if (j > r) {
            arr[k] = aux[i - l];
            i++;
        } else if (aux[i - l] < aux[j - l]) {
            arr[k] = aux[i - l];
            i++;
        } else {
            arr[k] = aux[j - l];
            j++;
        }
    }
}

//采用arr[l, r]
template<typename T>
void __mergeSort(T arr[], int l, int r) {

    if (l >= r) {
        return;
    }

    int mid = l + (r - l) / 2;

    //递归划左右分子区间
    __mergeSort(arr, l, mid);

    __mergeSort(arr, mid + 1, r);

    //优化点：当要合并的数组前后无序的时候才进行合并，有序直接返回。减少合并次数，提高效率
    if (arr[mid] > arr[mid + 1]) {
        //合并
        __merge(arr, l, mid, r);
    }

}

//采用arr[l, r]，当排序数据量较小的时候采用插入排序提高效率
template<typename T>
void __mergeSortBeat(T arr[], int l, int r) {

    if (r - l < 15) {
        insertionSortBeat(arr, l, r);
        return;
    }

    int mid = l + (r - l) / 2;

    //递归划左右分子区间
    __mergeSortBeat(arr, l, mid);

    __mergeSortBeat(arr, mid + 1, r);

    //优化点：当要合并的数组前后无序的时候才进行合并，有序直接返回。减少合并次数，提高效率
    if (arr[mid] > arr[mid + 1]) {
        //合并
        __merge(arr, l, mid, r);
    }

}

/**
 * 归并排序
 *
 * @param arr
 * @param n
 */
template<typename T>
void mergeSort(T arr[], int n) {

    __mergeSort(arr, 0, n - 1);
}

/**
 * 归并排序,优化版
 * 当数据量比较小的时候采用插入排序
 *
 * @param arr
 * @param n
 */
template<typename T>
void mergeSortBeat(T arr[], int n) {

    __mergeSortBeat(arr, 0, n - 1);
}


/**
 * 自低向上的归并排序
 *
 * @tparam T
 * @param arr
 * @param n
 */
template<typename T>
void mergeSortBU(T arr[], int n) {

    //sz 未每次比较的宽度，每完成一圈底部归并，比较宽度变为原来的2倍继续比较，直到宽度超过数组长度
    for (int sz = 1; sz < n; sz += sz) {
        //i 为比较区间的开始位置，每次增加两个比较宽度，进行下部分的比较，保证有两个区间可以进行比较，则第二区间必须存在：i+sz<n
        for (int i = 0; i + sz < n; i += sz + sz) {
            //优化点：1. 对于较小的数据集合使用插入排序；2. 对于已经有序的数组不在进行合并

            //归并操作
            //对arr[i,i+sz-1]和arr[i+sz,i+sz+sz-1]或arr[i+sz,n-1]进行归并,避免越界
            __merge(arr, i, i + sz - 1, min(i + sz + sz - 1, n - 1));
        }
    }

}

/**
 * 自低向上的归并排序加强版
 * 优化点：1. 对于较小的数据集合使用插入排序；2. 对于已经有序的数组不在进行合并
 *
 * @tparam T
 * @param arr
 * @param n
 */
template<typename T>
void mergeSortBUBeat(T arr[], int n) {

    //sz 未每次比较的宽度，每完成一圈底部归并，比较宽度变为原来的2倍继续比较，直到宽度超过数组长度
    for (int sz = 1; sz < n; sz += sz) {

        //i 为比较区间的开始位置，每次增加两个比较宽度，进行下部分的比较，保证有两个区间可以进行比较，则第二区间必须存在：i+sz<n
        for (int i = 0; i + sz < n; i += sz + sz) {

            //优化点：1. 对于较小的数据集合使用插入排序；2. 对于已经有序的数组不在进行合并
            if (sz < 15) {

                //使用插入排序进行优化小数据量排序
                insertionSortBeat(arr, i, min(i + sz + sz - 1, n - 1));
                break;
            }

            //优化点：2. 对于已经有序的数组不在进行合并
            if (arr[i + sz - 1] > arr[i + sz]) {

                //归并操作
                //对arr[i,i+sz-1]和arr[i+sz,i+sz+sz-1]或arr[i+sz,n-1]进行归并,避免越界
                __merge(arr, i, i + sz - 1, min(i + sz + sz - 1, n - 1));
            }
        }
    }
}

#endif //QUICKSORT_MERGESORT_H
